/*
 * @lc app=leetcode.cn id=912 lang=java
 *
 * [912] 排序数组
 *
 * https://leetcode.cn/problems/sort-an-array/description/
 *
 * algorithms
 * Medium (55.60%)
 * Likes:    586
 * Dislikes: 0
 * Total Accepted:    382.6K
 * Total Submissions: 687.5K
 * Testcase Example:  '[5,2,3,1]'
 *
 * 给你一个整数数组 nums，请你将该数组升序排列。
 * 
 * 
 * 
 * 
 * 
 * 
 * 示例 1：
 * 
 * 
 * 输入：nums = [5,2,3,1]
 * 输出：[1,2,3,5]
 * 
 * 
 * 示例 2：
 * 
 * 
 * 输入：nums = [5,1,1,2,0,0]
 * 输出：[0,0,1,1,2,5]
 * 
 * 
 * 
 * 
 * 提示：
 * 
 * 
 * 1 <= nums.length <= 5 * 10^4
 * -5 * 10^4 <= nums[i] <= 5 * 10^4
 * 
 * 
 */

// @lc code=start
class Solution {
    public int[] sortArray(int[] nums) {
        sort(nums, 0, nums.length - 1);
        return nums;
    }

    void sort(int[] nums, int low, int high) {
        if (low >= high) {
            return;
        }
        int base = nums[low];
        int i = low, j = high;
        while (i < j) {
            // 第一个比他小的
            while (i < j && nums[j] >= base) {
                j--;
            }
            // 第一个比他大的
            while (i < j && nums[i] <= base) {
                i++;
            }
            // 交换 // 有可能相等，相等时不交换
            if (i < j) {
                int t = nums[i];
                nums[i] = nums[j];
                nums[j] = t;
            }
        }
        nums[low] = nums[i];
        nums[i] = base;

        sort(nums, low, i - 1);
        sort(nums, i + 1, high);
    }
}
// @lc code=end
